package com.cn.algorithm02.class03;

/***
 * @author: hels
 * @description: 数组中有两个是奇数个， 其他都为偶数个, find two num
 * 要求时间复杂度为O(N) 额外空间复杂度O(1)
 * 意味着新建有限个变量
 **/
public class C04_TwoOdd {
    public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,4,5,5,5,5}; // 假设两个数字为a,b
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];  // eor = a^b;
        }

        int right1 = eor & (-eor); // 找出eor最右边的1，所以在该二进制位置，a和b不同
        int eor2 = 0;

        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & right1) != 0) { // 此处将数组中二进制位为1 和 为0 的进行区分后进行异或操作a^b^b^c^c = a
                eor2 ^= arr[i];
            }
        }

        System.out.println(eor2 + " , " + (eor ^ eor2));

    }
}
